package com.weizu.mst;

import java.util.LinkedList;
import java.util.Stack;

public class QueueDemo {

    public static void main(String[] args) {
        int number = new QueueDemo().localMinimum(new int[]{3, 1, 3, 4, 5, 6, 7});
        System.out.println(number);

    }

    public static void addElementToStack(Stack<Integer> stack, int[] arr) {
        for (int i : arr) {
            stack.push(i);
        }
    }


    // 查找数组中的局部最小值
    // 对于查找数组中的局部最小值可以分为如下三种情况，即：
    // - 对于数组首部：如果arr[0] < arr[1]，那么arr[0]为局部最小；
    // - 对于数组尾部：如果arr[n-2] > arr[n-1]，那么arr[n-1]为局部最小值；
    // - 对于其余任意位置i：需要满足arr[i-1]>arr[i]，且arr[i]<arr[i+1];
    // 那么编程应该首先考虑边界问题，最后对于非边界情况满足下图：
    //

    public int localMinimum(int[] arr) {
        int len = 0;
        if (arr == null || (len = arr.length) == 0 || len < 2) return -1;
        // 首尾边界情况
        if (arr[0] < arr[1]) return 0;
        if (arr[len - 1] < arr[len - 2]) return len - 1;

        int left = 0, right = arr.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (mid >= 1 && mid < len - 1 &&
                    arr[mid] < arr[mid + 1] && arr[mid] < arr[mid - 1]) { // 当前满足局部最小值
                return mid;
            } else if (mid >= 1 && arr[mid] > arr[mid - 1]) { // 局部最小值在左侧
                right = mid - 1;
            } else if (mid < len - 1 && arr[mid] > arr[mid + 1]) { // 局部最小值在右侧
                left = mid + 1;
            }
        }
        return -1;
    }


    /**
     * 给定一个整形数组，和一个滑动窗口，求从左到右的每次的窗口的最大值
     * 【要求】时间复杂度 O(n)
     *
     * @param arr        数组
     * @param windowSize 滑动窗口大小
     * @return 每次的窗口的最大值
     */
    public int[] getMaxWindow(int[] arr, int windowSize) {
        int size = arr.length - windowSize + 1;
        int[] result = new int[size];
        LinkedList<Integer> deque = new LinkedList<Integer>();
        int index = 0;
        for (int i = 0; i < arr.length; i++) {
            while (!deque.isEmpty() && arr[deque.getLast()] < arr[i]) {
                deque.removeLast();
            }
            deque.addLast(i);
            if (deque.getFirst() == i - windowSize) {
                deque.removeFirst();
            }
            if (i >= windowSize - 1) {
                result[index++] = arr[deque.peekFirst()];
            }
        }
        return result;
    }
}
